package com.yehui.algorithm.sword;

/**
 * 统计一个数字在排序数组中出现的次数
 * Created by XuChunH on 2016/9/18.
 */
public class GetNumberOfK {

    public int solution(int[] array, int k) {
        if(array == null || array.length == 0){
            return 0;
        }
        return getNumber(array, 0, array.length - 1, k);
    }

    private int getNumber(int[] array, int start, int end, int target){
        if(start > end){
            return 0;
        }
        int mid = (start + end) / 2;
        int count = 0;
        if(array[mid] == target){
            count++;
            for (int i = mid - 1; i >= 0; i--) {
                if(array[i] != target){
                    break;
                }
                count++;
            }
            for (int i = mid + 1; i < array.length; i++) {
                if(array[i] != target){
                    break;
                }
                count++;
            }
            return count;
        }else if(target > array[mid]) {
            return getNumber(array, mid + 1, end, target);
        }else {
            return getNumber(array, start, mid - 1, target);
        }
    }

}
